While a computer system is operating, resources are spent to manage various aspects of the system. Systems may be configured before operation to prioritize certain resources of the system over others. Other systems may include an embedded system that configures system resources. Embedded systems typically maintain a dedicated function within a larger mechanical, electrical or computer system, often with real-time computing constraints.
Embedded systems include, for example, hardware components such as programmable logic devices (PLDs). PLDs, including field-programmable gate arrays (FPGAs), are integrated circuits (ICs) that can be programmed to implement user-defined logic functions.
FPGAs are an important and commonly used circuit element in conventional electronic systems. FPGAs are attractive for use in many designs in view of their low non-recurring engineering costs and rapid time to market. FPGA circuitry is also being increasingly integrated within other circuitry to provide a desired amount of programmable logic. Many applications can be implemented using FPGA devices without the need of fabricating a custom integrated circuit.
The Discrete Radon Transform (DRT) is an essential component of a wide range of applications in image processing. Applications of the DRT include the classic application of reconstructing objects from projections such as in computed tomography, radar imaging and magnetic resonance imaging. More recently, the DRT has also been applied in image denoising, image restoration, texture analysis, line detection in images, and encryption.
A popular method for computing the DRT involves the use of the Fast Fourier Transform (FFT). First, the 2-D FFT is used for computing the 2-D FFT spectrum. Second, the 2-D FFT spectrum is sampled along different radial lines through the origin. Then, the 1-D inverse FFT is used for estimating the DRT. This direct approach based on the FFT suffers from many artifacts. Assuming that the DRT is computed directly, an exact inversion algorithm has been proposed including improvements related to the elimination of interpolation calculations. However, the DRT requires the use of expensive floating point units for implementing the FFTs. Floating point units require significantly larger amounts of hardware resources than fixed point implementations.
The Discrete Periodic Radon Transform (DPRT) has been extensively used in applications that involve image reconstructions from projections. Beyond classic applications, the DPRT can also be used to compute fast convolutions that avoid the use of floating-point arithmetic associated with the use of the Fast Fourier Transform. Unfortunately, the use of the DPRT has been limited by the need to compute a large number of additions and the need for a large number of memory accesses.
Fixed point implementations of the DRT can be based on the DPRT. Previous research as resulted in the introduction of the forward DPRT algorithm for computing the 2-D Discrete Fourier Transform as well as a sequential algorithm for computing the DPRT and its inverse for prime sized images.
Similar to the continuous-space Radon Transform, the DPRT satisfies discrete and periodic versions of the Fourier slice theorem and the convolution property. Thus, the DPRT can lead to efficient, fixed-point arithmetic methods for computing circular and linear convolutions. The discrete version of the Fourier slice theorem provides a method for computing 2-D Discrete Fourier Transforms based on the DPRT and a minimal number of 1-D FFTs.
Scalable solutions for embedded systems are desired that can deliver different solutions based on one or more constraints. As an example, it is desirable to have a low-energy solution when there is a requirement for long-time operation and a high-performance solution when there is no power (or energy) constraint. More specifically, scalable solutions are desired that can allocate hardware resources based on constraints, for example minimize energy consumption, minimize bitrate requirements, increase accuracy, increase performance, and/or improve image quality.
There is a demand for DPRT algorithms that are both fast—the computation provides the result in the minimum number of cycles—and scalable—the approach provides the fastest implementation based on the amount of available resources. The invention satisfies this demand.